1. Technical Field
This invention relates in general to optimizing compilers, and in particular to redundant load elimination optimization on optimizing compilers.
2. Description of the Related Art
Optimizing compilers optimize the executable code of a computer program by rearranging the code sequences to take maximum advantage of the computer architecture and the specific configuration of the individual computer program. Of particular importance in optimizing compilers is the elimination of redundant loads. Redundant loads are loads from memory into a CPU register which have taken place previously in the compiled program. Redundant load elimination in optimizing compilers recognizes and enhances the situation in which the result of a memory load instruction is already available in a CPU register, and thus, an additional load instruction for that value is not necessary. Such redundant load elimination reduces memory traffic requirements to yield more efficient code.
Redundant load elimination is even more important for modern compilers which implement loop reordering for enhanced cache behavior and advanced optimization such as Pipeline Scheduling (PS). Pipeline Scheduling schedules the execution of loop iterations in overlapping fashion so that they may be pipelined through the processor. For loops with recurrences, the memory accesses in a subsequent iteration (i+1) are frequently made to the same locations accessed by a previous iteration (i).
Redundant Load Elimination recognizes when the target of a Load Instruction is the same as a previous Store or Load Instruction. By saving the previous argument in a register, the LOAD is eliminated from the compiled program, creating more efficient code. Furthermore, many modern compilers use preprocessors to enhance cache locality by producing stride-1 array accesses. The application of Pipeline Scheduling to these loops is likely to introduce further opportunities for Redundant Load Elimination.
In traditional vectorizing/parallelizing compilers, Load/Store elimination is usually implemented via pattern recognition. This type of optimization is complex and burdensome, and significantly adds to compiler processing. It would be desirable to have a Redundant Load Elimination optimization which is simple to implement, and further, takes advantage of processing already performed by modern compilers so that the addition of the Redundant Load Elimination optimization is a simple extension of modern optimizing compilers.